home *** CD-ROM | disk | FTP | other *** search
/ Loadstar 12 / 012.d81 / lcm article < prev    next >
Encoding:
Text File  |  1985-01-01  |  1.9 KB  |  125 lines
  1.  
  2.       THE LCM OF TWO INTEGERS
  3.  
  4.  
  5.  
  6.  
  7. DEFINITION: The LEAST COMMON MULTIPLE
  8.  
  9. (or LCM) of two integers, A and B, is
  10.  
  11. a positive integer M satisfying:
  12.  
  13.  i) A divides M and B divides M.
  14.  
  15. ii) if M' is any other integer
  16.     such that A divides M' and B
  17.     divides M', then M' is also
  18.     divisible by M.
  19.  
  20. REMARK:  The LCM of two positive
  21.  
  22. integers exists.
  23.  
  24. PROOF:  The set of all positive
  25.  
  26. integers N such that A divides N,
  27.  
  28. and B divides N is not empty. (WHY?)
  29.  
  30. It is bounded below by 0.  Therefore,
  31.  
  32. it must have a least element.  We have
  33.  
  34. used the fact that the positive
  35.  
  36. integers are WELL ORDERED again.
  37.  
  38. If you couldn't answer the WHY? above,
  39.  
  40. set N=AB.  Prove that both A and B
  41.  
  42. always divide AB.
  43.  
  44. THEOREM:  Let A and B be two positive
  45.  
  46. integers, and let G be their GCD.
  47.  
  48. Then the LCM, M, of A and B is given
  49.  
  50. by
  51.  
  52.        M = AB/G.
  53.  
  54. OUTLINE OF THE PROOF: First show that
  55.  
  56. A divides M and B divides M. ( This is
  57.  
  58. pretty easy.  Use the fact that A/G
  59.  
  60. and B/G are integers.)
  61.  
  62. Then show that if M' is divisible by
  63.  
  64. both A and B, it must be divisible by
  65.  
  66. AB/G.  That will show that AB/G is the
  67.  
  68. LCM of A and B. (HINT: write AB/G as
  69.  
  70. (A)(B/G) and use the following
  71.  
  72. result.)
  73.  
  74. LEMMA: If A, B, and C are positive
  75.  
  76. integers, such that A divides C and
  77.  
  78. B divides C, and if (A,B)=1, then
  79.  
  80. AB divides C.
  81.  
  82. PROOF OF LEMMA: Since (A,B)=1, there
  83.  
  84. exist integers D and E such that
  85.  
  86. (1)         AD + BE = 1.
  87.  
  88. Then multiplying the above equation
  89.  
  90. by C,
  91.  
  92. (2)        CAD + CBE = C.
  93.  
  94. Since A and B divide C, there exist
  95.  
  96. integers K and L such that
  97.  
  98. (3)      C = KA and C = LB.
  99.  
  100. Substituting these values for C in the
  101.  
  102. left-hand side of equation (2),
  103.  
  104. (4)      LBAD + KABE = C
  105.  
  106. Factoring AB from both terms on the
  107.  
  108. left,
  109.  
  110. (5)       AB(LD + KE) = C.
  111.  
  112. Thus AB divides C.
  113.  
  114. REMARK: Notice that the fact that the
  115.  
  116. GCD of A and B being equal to 1 is
  117.  
  118. really necessary.  As an example,
  119.  
  120. 12 is divisible by 4 and 6, but 12 is
  121.  
  122. NOT divisible by (4)(6) = 24.
  123.  
  124. --------------------------------------
  125.